package com.zang.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZVerify
 * @since 2022/10/31 08:37
 * @see <a href="https://leetcode.cn/problems/binary-tree-paths/comments/">...</a>
 **/
public class 二叉树的所有路径 {

    List<String> list = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {

        if (root==null) return list;
        // 保存节点
        Deque<TreeNode> nodeArrayList = new LinkedList<>();
        // 同步节点所经过的路径
        Deque<String> strings = new LinkedList<>();
        nodeArrayList.addLast(root);
        strings.addLast(String.valueOf(root.val));

        while (!nodeArrayList.isEmpty()) {
            for (int i = 0; i < nodeArrayList.size(); i++) {
                TreeNode treeNode = nodeArrayList.pollLast();
                String s = strings.pollLast();
                if (treeNode.left==null && treeNode.right==null){
                    list.add(s);
                }else {
                    if (treeNode.left!=null) {
                        // 相当于一个map，两个队列同步一起维护节点和路径
                        nodeArrayList.addLast(treeNode.left);
                        strings.add(s+"->"+treeNode.left.val);
                    }
                    if (treeNode.right!=null) {
                        nodeArrayList.addLast(treeNode.right);
                        strings.add(s+"->"+treeNode.right.val);
                    }
                }
            }
        }
        return list;
    }


}
